import collections

# class Solution(object):
#     def findItinerary(self, tickets):
#         """
#         :type tickets: List[List[str]]
#         :rtype: List[str]
#         """
#         d = collections.defaultdict(list)
#         for ticket in tickets:
#             d[ticket[0]].append(ticket[1])
#         m = len(tickets)
#         out = []
#         for key in d:
#             d[key].sort()
#
#         def search(point, k):
#             out.append(point)
#             if k == m:
#                 return True
#             n = len(d[point])
#             index = 0
#             while index < n:
#                 if index > 0 and d[point][index] == d[point][index - 1]:
#                     index += 1
#                 else:
#                     next_point = d[point][index]
#                     del d[point][index]
#                     flag = search(next_point, k + 1)
#                     if flag:
#                         return True
#                     else:
#                         d[point].insert(index, next_point)
#                         index += 1
#             out.pop()
#             return False
#
#         search('JFK', 0)
#         return out

# 第二次做，欧拉回路方法
import collections


class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        edges = collections.defaultdict(list)
        for u, v in tickets:
            edges[u].append(v)
        for u in edges:
            edges[u].sort(reverse=True)
        ans = []

        def dfs(node):
            while edges[node]:
                v = edges[node].pop()
                dfs(v)
            ans.append(node)

        dfs('JFK')
        ans.reverse()
        return ans


data = Solution()
tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
print(data.findItinerary(tickets))
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
print(data.findItinerary(tickets))
